Decision and approximation complexity for identifying codes and locating-dominating sets in restricted graph classes

An identifying code is a subset of vertices of a graph with the property that each vertex is uniquely determined (identified) by its nonempty neighbourhood within the identifying code. When only vertices out of the code are asked to be identified, we get the related concept of a locating-dominating set. These notions are closely related to a number of similar and well-studied concepts such as the one of a test cover. In this paper, we study the decision problems Identifying Code and Locating-Dominating Set (which consist in deciding whether a given graph admits an identifying code or a locating-dominating set, respectively, with a given size) and their minimization variants Minimum Identifying Code and Minimum Locating-Dominating Set. These problems are known to be NP-hard, even when the input graph belongs to a number of specific graph classes such as planar bipartite graphs. Moreover, it is known that they are approximable within a logarithmic factor, but hard to approximate within any sub-logarithmic factor. We extend the latter result to the case where the input graph is bipartite, split or co-bipartite: both problems remain hard in these cases. Among other results, we also show that for bipartite graphs of bounded maximum degree (at least 3), the two problems are hard to approximate within some constant factor, a question which was open. We summarize all known results in the area, and we compare them to the ones for the related problem Dominating Set. In particular, our work exhibits important graph classes for which Dominating Set is efficiently solvable, but Identifying Code and Locating-Dominating Set are hard (whereas in all previous works, their complexity was the same). We also introduce graph classes for which the converse holds, and for which the complexities of Identifying Code and Locating-Dominating Set differ.     

Approximation of quantum assemblages

In this paper, we derive a set of projectors on a large Hilbert space which can universally work for approximating quantum assemblages with binary inputs and outputs. The dimension of the Hilbert space depends on the accuracy of the approximation.     

Aqueous solutions of ionic liquids. Description of osmotic coefficients within the Binding Mean Spherical Approximation

The Binding Mean Spherical Approximation (BiMSA) is used to describe osmotic coefficients of aqueous solutions of salts containing imidazolium cations and bulky anions over the whole concentration range at temperature in the range (25 to 60) °C. A total of 13 salts have been considered altogether. The ion diameters, the permittivity of solution and the association constant were taken as adjustable parameters. Ionic liquids are described as being weakly associated in water, and association constants values obtained within the BiMSA model are in good agreement with those from the literature. Diameter values were assigned to 1-alkyl-3-methylimidazolium cations. The adjusted values obtained for the cation diameters increased with the number of carbons on the alkyl chain. For all systems studied, average relative deviations were found to be satisfactory.     

广义线性多乘积问题的完全多项式时间近似算法

本文针对广义线性多乘积极小化问题,通过一系列的线性规划问题的解提出一种求其全局最优解的完全多项式时间近似算法,并给出该算法的计算复杂性,且数值算例验证该算法是可行的.     

Approximation algorithms from inexact solutions to semidefinite programming relaxations of combinatorial optimization problems

Semidefinite relaxations of certain combinatorial optimization problems lead to approximation algorithms with performance guarantees. For large-scale problems, it may not be computationally feasible to solve the semidefinite relaxations to optimality. In this paper, we investigate the effect on the performance guarantees of an approximate solution to the semidefinite relaxation for MaxCut, Max2Sat, and Max3Sat. We show that it is possible to make simple modifications to the approximate solutions and obtain performance guarantees that depend linearly on the most negative eigenvalue of the approximate solution, the size of the problem, and the duality gap. In every case, we recover the original performance guarantees in the limit as the solution approaches the optimal solution to the semidefinite relaxation.     

An FPTAS for scheduling with resource constraints

We study a basic scheduling problem with resource constraints: A number of jobs need to be scheduled on two parallel identical machines with the objective of minimizing the makespan, subject to the constraint that jobs may require a unit of one of the given renewable resources during their execution. For this NP-hard problem, we develop a fully polynomial-time approximation scheme (FPTAS). Our FPTAS makes a novel use of existing algorithms for the subset-sum problem and the open shop scheduling problem.     

The non-Markovian nature of nested logit choice

Discrete choice models are widely used for understanding how customers choose between a variety of substitutable goods. We investigate the relationship between two well studied choice models, the Nested Logit (NL) model and the Markov choice model. Both models generalize the classic Multinomial Logit model and admit tractable algorithms for assortment optimization. Previous evidence indicates that the NL model may be well approximated by, or be a special case of, the Markov model. We establish that the Nested Logit model, in general, cannot be represented by a Markov model. Further, we show that there exists a family of instances of the NL model where the choice probabilities cannot be approximated to within a constant error by any Markov choice model.     

三阶非线性发展方程的线性化有理逼近方法

研究了三阶非线性发展方程的初边值问题的解。采用基于Sinc函数的微分求积法发展了线性化有理逼近方法。通常的配点法不适用于上述三阶问题的求解。本文把提出的方法用于求解KdV方程,取得了良好的效果。